package C055;

import java.util.Arrays;

/**
 * ClassName: C03
 * Package: C055
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/4/10 15:09
 * @Version 1.0
 * @Since 1.0
 */
public class C03 {
    public static void main(String[] args) {

        int[] arr1 = {5,9,8,5,9};
        int[] arr2 = {1,6,4,2,6};
        System.out.println(maxTaskAssign(arr1, arr2, 1, 5));
        System.out.println(Integer.MAX_VALUE);
    }


    /*
    n == tasks.length
    m == workers.length
    1 <= n, m <= 5 * 104
    0 <= pills <= m
    0 <= tasks[i], workers[j], strength <= 109
     */
    static int MAXLEN = 100001;
    static int[] deque = new int[MAXLEN];
    static int h, t;
    static int l, r, m, n;
    static int[] ts, ws;

    public static int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {
        l = 0;
        n = Math.min(tasks.length, workers.length);
        r = n;
        Arrays.sort(tasks);
        Arrays.sort(workers);
        ts = tasks;
        ws = workers;
        int ans = 0;
        while (l <= r) {
            m = l + ((r - l) >> 1);
            if (f(0, m - 1, ws.length - m, ws.length - 1, strength, pills)) {
                ans = m;
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return ans;
    }


    private static boolean f(int tl, int tr, int wl, int wr, int s, int p) {
        h = t = 0;
        int count = 0;
        for (int i = tl, j = wl; j <= wr; j++) {
            // 解锁任务
            while (i <= tr && ws[j] >= ts[i]) {
                deque[t++] = i++; // 因为已经排序了，这里的单调性是具备的
            }
            // 队列能做的任务
            if (h < t && ts[deque[h]] <= ws[j]) {
                h++; // 没吃药，队头清空
            }else {
                // 吃药
                while(i <= tr && ws[j] + s >= ts[i]) {
                    deque[t++] = i++;
                }
                // 做任务
                if(h < t) { // 如果吃药任务依旧是做不了，队列一定为空
                    count ++;
                    t--; // 吃药队尾清空
                }else {
                    return false;
                }
            }
        }
        return count <= p;
    }
}
